class Solution {

    //向下调整
    public  void siftDown(int[] arr,int parent,int length){

        int child = 2 * parent + 1;
        int size = length;

        while(child < size){
           //判断是否有右孩子，并判断是否更新
            if(child + 1 < size &&  arr[child] > arr[child + 1]){
                child = child + 1;//右孩子小
            }

            //交换
            if(arr[parent] > arr[child]){
                int t = arr[parent];
                arr[parent] = arr[child];
                arr[child] = t;
                //更新parent
                parent = child;
                child =  2 * parent + 1;
            }else break;
        }
    }

    public void createHeap(int[] arr){
        int root = (arr.length - 2) / 2;
        for (; root >= 0 ; root--) {
            siftDown(arr,root,arr.length);
        }
    }

    public void HeapSort(int[] arr){
        if(arr == null || arr.length == 1) return;

        int length = arr.length;
        //使用for循环遍历交换
        for (int i = length - 1; i > 0 ; i--) {
            //1.交换
            int tem = arr[0];
            arr[0] = arr[i];
            arr[i] = tem;

            //2.向下调整

            siftDown(arr,0,--length);
        }

    }
    public  int[] smallestK(int[] arr, int k) {

        if(k == 0) return new int[0];

        //1.创建小堆
        createHeap(arr);

        //2.堆排序
        HeapSort(arr);

        //3.获取前k个数
         k = Math.min(k,arr.length);
         int[] ret = new int[k];

         int i = 0,j = 0;
         while(k-- != 0){
             ret[i++] = arr[j++];
         }
         return ret;
    }

    public static void main(String[] args) {

        Solution solution = new Solution();
        int[] arr = {24,12,45,11,56,77,96};
        int[] tem = solution.smallestK(arr,3);

        System.out.println();
        System.out.print("arr数组中最大的前" + 3 + "个数是：");
        for(int p : tem){
            System.out.print(p + " ");
        }

    }

}